#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
template<class k>
struct DefaultHashFunc
{
	size_t operator()(const k& data)
	{
		return (size_t)data;
	}
};

template<>
struct DefaultHashFunc<string>
{
	size_t operator()(const string& str)
	{
		int num = 0;
		for (auto ch : str)
		{
			num = 131 * num + ch;
		}
		return num;
	}
};
template<class k, class v>
struct Hashnode
{
	pair<k, v> _data;
	Hashnode<k, v>* _next;
	Hashnode(const pair<k, v>& kv)
		:_next(nullptr)
		, _data(kv)
	{}
};

template<class k, class v, class HashFunc = DefaultHashFunc<k>>
class Hashtable
{
	typedef Hashnode<k, v> Node;
public:
	Hashtable()
	{
		_table.resize(10, nullptr);
	}

	~Hashtable()
	{
		for (int i = 0; i < _table.size(); i++)
		{
			if (_table[i])
			{
				Node* cur = _table[i];
				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
		}
	}

	bool insert(const pair<k, v>& kv)
	{
		if (Find(kv.first)) return false;
		HashFunc fc;
		if (_table.size() == _n)
		{
			size_t newsize = _table.size() * 2;
			vector<Node*> newtable;
			newtable.resize(newsize, nullptr);
			for (size_t i = 0; i < _table.size(); i++)
			{
				if (_table[i])
				{
					Node* cur = _table[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t pos = fc(cur->_data.first) % newsize;
						cur->_next = newtable[pos];
						newtable[pos] = cur;
						cur = next;
					}
					_table[i] = nullptr;
				}
			}
			newtable.swap(_table);
		}
		size_t pos = fc(kv.first) % _table.size();
		Node* node = new Node(kv);
		node->_next = _table[pos];
		_table[pos] = node;
		_n++;
		return true;
	}

	Node* Find(const k& key)
	{
		HashFunc fc;
		size_t pos = fc(key) % _table.size();
		if (_table[pos])
		{
			Node* cur = _table[pos];
			while (cur)
			{
				if (cur->_data.first == key)
					return cur;
				cur = cur->_next;
			}
		}
		return nullptr;
	}

	bool erase(const k& key)
	{
		HashFunc fc;
		size_t pos = fc(key) % _table.size();
		if (_table[pos])
		{
			Node* cur = _table[pos];
			Node* prev = nullptr;
			while (cur)
			{
				if (cur->_data.first == key)
				{
					if (prev == nullptr)
					{
						_table[pos] = cur->_next;
					}
					else
					{
						prev->_next = cur->_next;
					}
					delete cur;
					cur = nullptr;
					_n--;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
		}
		return false;
	}

	void Print()
	{
		for (size_t i = 0; i < _table.size(); i++)
		{
			cout << '[' << i << ']' << "->";
			Node* cur = _table[i];
			while (cur)
			{
				cout << cur->_data.first << ":" << cur->_data.second << "->";
				cur = cur->_next;
			}
			cout << "nullptr" << endl;
		}
		cout << endl;
	}
private:
	vector<Node*> _table;
	size_t _n = 0;
};

